Raster Image Processing is the process and the means of turning vector digital information, such as an Adobe® PostScript® file, into a high-resolution raster image. The Raster Image Processor (RIP) takes the digital information about fonts and graphics that describes the appearance of a document and translates the information into an image composed of individual pixels that the imaging device such as a printer can output. A number of types of Raster Image Processors are known to the art. These include frame-store RIP's, band-store RIP's and tile-order RIP's.
In the tile RIP, the page is divided up into square tiles. Each tile is fully rendered before the RIP starts rendering the next tile. With such a RIP, the RIP output compressor may start compression of a rendered tile as soon as it is available, provided that the compressor can accept data in tile order.
Pixel data generated by a RIP can belong to a number of different region types namely text, graphic, pattern and image regions. Each region type has different characteristics and hence compression requirements. Pixels that form characters, symbols and other glyphs are referred to as text regions. Pixels that form large regions of the same colour as evident in many block diagrams, charts and clip art are referred to as graphic regions. Text regions and graphic regions both contain a single colour per region and require the transitions between regions to be defined accurately in order to maintain sharp edges. Pattern regions are pixels that contain a regular or random pattern of small dots or blobs to simulate a shading effect. They typically only use 2 colours, but contain many sharp transitions in colour. Due to the very small size and spacing of the dots, it is not particularly critical to retain this information exactly. The effect that is created by the dots takes advantage of the human eye's tendency to average fine detail. Image regions contain many colours per region which vary more smoothly than the transitions between colours in graphic or text regions. These regions contain a large quantity of data due to the constantly changing colours within the region.
A common practice is to compress the RIP output to reduce the amount of memory required and hence the cost of hardware in a printing device. Many methods with various advantages and disadvantages have been suggested to achieve this compression. When choosing a compression method, it is important to use a method that is appropriate for the type of data being compressed. These methods can broadly be categorized as either lossy or lossless.
One class of lossy RIP output compression algorithms is the pixel-based methods, such as JPEG and wavelet compression. These algorithms are able to achieve high compression ratios by discarding information that is not visually significant. This achieves good compression ratios and acceptable visual quality for natural images, however, documents containing sharp transitions in colour such as basic text or graphics can suffer from the introduction of visible artifacts.
The majority of lossless compression algorithms can be broadly categorized as pixel-based or edge-based. Lossless pixel-based methods such as JPEG-LS suffer from the same drawbacks as lossy pixel-based methods. As resolution and colour depth increases, these algorithms become prohibitively memory expensive. The advantage of lossless compression is that the output is of high quality. This is important for text and graphic regions where sharp transitions in colour must be maintained and the sort of artifacts caused by most lossy algorithms avoided. The disadvantage of lossless compression is that worst-case jobs will cause the compressed size to be larger than the raw size.
Edge-based (vector-based) algorithms are generally lossless and therefore preserve sharp transitions in colour. Text regions and graphic regions contain a single colour and can therefore be represented very efficiently using edge-based algorithms since a large area of many pixels can be described with only a single edge. These algorithms are less affected by increases in resolution or bit depth since the number of edges does not increase as the resolution increases. However, natural images do not compress well with edge-based algorithms and may even cause the compressed size to be larger than the raw size.
Pattern data can be effectively coded by some lossless, pixel-based methods that use predictive coding. This is true if the pattern is uniform, however, pattern regions that contain random patterns result in a poor compression ratio.
No lossy or lossless method alone produces a satisfactory outcome for the compression of RIP output which can contain a wide variety of different requirements across a single page. A combination or hybrid of lossless and lossy methods is one way to achieve better results.
The lossless method preserves the sharp colour transitions while the lossy method provides strong compression of regions with many colours. This can be an effective method of gaining high compression while maintaining high quality. This requires some method of identifying which regions should be encoded losslessly and which should be encoded lossily.
Usually, lossless encoding is used for flat regions. Flat regions are text or graphics regions which typically consist of a single colour which is outlined by a sharp edge at page resolution.
Usually, lossy encoding is used for regions of pixels that form a photographic image. These image regions contain a wide variety of colours that typically do not change markedly from one pixel to the next. The boundary of an image region must still be retained accurately since the human visual system will treat the boundary between an image region and a flat region much the same as the boundary between two flat regions. However, the pixels within an image region do not need to be preserved exactly since the human visual system is less sensitive to small variations in colour or luminance within an image region.
Pattern data may be compressed with either a lossy or a lossless method. The decision of which method to use is usually based on analysing the performance of the chosen lossy and lossless algorithms when compressing pattern data.
One method of applying a combination of lossy and lossless compression is to analyse blocks of pixels (usually tiles) and choose the most appropriate method for each block. This method has some advantages over just using a single compression method for the whole page, but it can still cause visible artefacts since many blocks will contain a mixture of flat and image regions.
In order to solve this problem, the Mixed Raster Content standard (MRC) (ITU recommendation T.44) outlines a standard way of defining the pixel type of each pixel in mixed-raster content documents (documents containing flat regions and photographic images). The page is split into three planes to allow a lossless and lossy compression method to be applied to two of the planes while the third plane is used as a binary mask to select between the first two planes. Unfortunately, no provisions are made for detecting text with background images or for the presence of text within images. Furthermore, the document background basically must be white or bright. These are unsatisfactory constraints for RIP output compression.
The cost of memory required to store the RIP output is a critical factor in the overall cost of a printing system. While it has already been stated that RIP output compression is necessary, a further requirement is that the maximum size of the compressed output is fixed so that hardware costs can be kept low. In other words, it is important to use a compression algorithm characterised as guaranteed fit. One approach to achieving guaranteed fit is to compress the image multiple times, increasing the compression strength successively until the data fits in the fixed output. For this method, the complete page must be held in memory before compression. Then, if the fixed memory size is exceeded, the page is recompressed with different settings until the image fits in the allocated memory. This method does not reduce memory requirements since the complete RIP output is being stored prior to compression. Also, this method can be expensive in processing time if multiple compression passes are required.
U.S. Pat. No. 5,638,498 (Tyler, et. al.) granted Jun. 10, 1997 discloses a method and apparatus for reducing storage requirements for display data. Data objects to be displayed are organized into display lists and each data object includes an object type, such as text, graphic, and image. The data objects are rasterised into an uncompressed band buffer and divided into non-intersecting bitmap regions each identified with one or more object types. Each non-empty region is assigned a compression algorithm dependent upon the type of the region and specified compression constraints. The regions are combined with each other into larger regions if appropriate, and each region is compressed using its assigned compression algorithm into a compressed band buffer, thus reducing the required storage space for the data objects. The compressed data is decompressed in scan line order with a selected decompression algorithm corresponding to the assigned compression algorithms to produce uncompressed output data. The uncompressed output data is supplied to an output display device for display. However, the method used to define the regions is based on an object level assessment and not a pixel level assessment of the region. This method suffers from being a coarse method of selecting the compression method. Pixel based selection method allows a much finer granularity.
U.S. Pat. No. 6,324,305 (Holladay, et. al.) granted Nov. 27, 2001 and U.S. Pat. No. 6,330,362 (Venkateswar) granted Dec. 11, 2001 disclose methods of compressing multi-level screened images. In particular, a method is disclosed of compressing a colour or gray scale pixel map representing a document using an MRC format including a method of segmenting an original pixel map into two planes, and then compressing the data of each plane in an efficient manner. The image is segmented such that pixels that compress well under a lossy compression technique are placed on one plane and pixels that must be compressed losslessly are placed on another plane. Lossy compression is then applied to the lossy pixel plane while lossless compression is applied to the lossless pixel plane. It suffers from the requirement to losslessly encode the binary image selection plane as metadata in order to reconstruct the image leading to an increase in memory resources. The methods described also increase the quantization of image regions depending on remaining memory resource. These methods have a number of weaknesses. Firstly, the compression factor may vary across the page, resulting in areas of different visual quality. Secondly, areas of low complexity will utilise too much memory, while areas of high complexity will not have enough memory available when needed. Thirdly, the aim of these methods is to fill a set memory size, so even simple pages will require a large amount of memory.
U.S. Pat. No. 5,982,937 (Accad) granted Nov. 9, 1999 discloses an apparatus and method for hybrid compression of raster data. Patches of connected pixels of the same colour are identified. Patches of at least a predetermined sized, typically corresponding to text or line art objects, are subjected to a lossless compression. Patches below the predetermined size, typically corresponding to image or photo objects, are substantially subjected to a lossy compression. The patch predetermined size controls the mix of lossless and lossy compression procedures. Optimum compression is achieved by maximizing the lossless compression while attaining a targeted compression ratio. Various features include efficient recognition and encoding of patches, refined treatment of the boundaries between the lossless- and the lossy-compressed pixels, adaptive compression ratio control, and fail-safe compression provisions. Rate control is achieved by varying compression factors as memory resources become exhausted leading to uneven quality across the page.
U.S. Pat. No. 6,980,693 (Horie) granted Dec. 27, 2005 discloses an image coding method that compresses an image read through an optical system. An image separation section divides tile (macro block) units of the image into photographic image tiles and character image tiles. A layer separation section performs layer separation pixel by pixel to classify each pixel into pixels belonging to a background and pixels belonging to a foreground. Approximation processors alleviate an increase of entropy, due to layer separation through approximation processing, and carry out JPEG-like processing on photographic images.
To summarise, the current state of published art in hybrid compression of mixed-content documents does not achieve satisfactory performance in all respects. The granularity of the selection is too coarse or the memory/computation overheads are unacceptable. Moreover, achieving ‘guaranteed-fit’ memory size while preserving even quality over the page has proved elusive.
The above discussion relates to documents which form public knowledge by virtue of their publication. Such should not be interpreted as admission by the present inventors or applicant that such documents form part of the common general knowledge in the art.